package com.cat.dynamicPlanning;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/
 * @create 2025/8/29 20:20
 * @since JDK17
 */

public class Solution22 {
    int n, m, ans;
    int[][]dire = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int[][]dp = new int[201][201];
    public int f(int[][] matrix, int x, int y) {
        if (dp[x][y] != -1) {
            return dp[x][y];
        }
        int ans = 0;
        for (int i = 0; i < 4; i++) {
            int nx = x + dire[i][0], ny = y + dire[i][1];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m || matrix[x][y] >= matrix[nx][ny]) {
                continue;
            }
            ans = Math.max(ans, 1 + f(matrix, nx, ny));
        }
        return dp[x][y] = ans;
    }



    public int longestIncreasingPath(int[][] matrix) {
        n = matrix.length;
        m = matrix[0].length;
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], 0, m, -1);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans = Math.max(ans, f(matrix, i, j));
            }
        }
        return ans;
    }
}
